All Questions
6 questions
11votes
2answers
2kviews
Counterexample to max-flow algorithms with irrational weights?
It is known that the basic Ford-Fulkerson maximum flow algorithm need not halt if some of the weights are irrational, and this also holds with the fat pipe heuristic (due to Edmonds and Karp). In fact,...
- 38.9k
2votes
1answer
1kviews
Efficient recalculation of the maximum flow when edge capacities are reduced
Assume that we have a (directed) graph $G(V \cup \{s, t\}, E)$ and an (integer) capacity function $c : E \mapsto \mathbb{N}$. Let $f : E \mapsto \mathbb{N}$ be a maximum $s-t$ flow on this graph. ...
- 195
4votes
3answers
9kviews
Fastest polynomial time algorithm for solving minimum cost maximum flow problems in bipartite graphs
Orlin's algorithm is known to solve minimum cost maximum flow problems in $O(|E|^2 \log |V| + |E| \; |V| \log^2 |V|)$ time, where $|E|$ and $|V|$ respectively denote the cardinalities of the edge and ...
- 195
8votes
1answer
1kviews
Goldberg&Tarjan: How to find a blocking flow in a graph
I want to implement the Goldberg & Rao algorithm for finding a maxflow in a graph. My problem is the update step where every paper and report is stating "In the resulting graph, find a ...
32votes
3answers
3kviews
Are any of the state of the art Maximum Flow algorithms practical?
For the maximum flow problem, there seem to be a number of very sophisticated algorithms, with at least one developed as recently as last year. Orlin's Max flows in O(mn) time or better gives an ...
- 421
2votes
2answers
437views
Viapath as a maximum flow problem
Let $G = (V, E)$ be a graph and $a$, $b$, $x$ $\in V \ $ different vertices. I have seen stated that the problem of finding a simple path from $a$ to $b$ passing through $x$ can be formulated as a ...
- 31
